package mx.itesm.minAFN;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;

import mx.itesm.minAFN.utils.ArrayUtils;
import mx.itesm.minAFN.utils.StringUtils;

public class AFN extends Hashtable<String, AFNState> {

	public static String epsilon = "*"; 
	private static String epsilonClosure = "**";
	private static String epsilonClosureTemp = "***";
	
	private HashSet<String> language = new HashSet<String>();
	
	public AFN() {
		super();
	}
	
	public void addState(AFNState state){
		this.put(state.getStateName(), state);
	}
	
	public AFN minimize(){
		for (AFNState state : this.values()) {
			for (String key : state.getTransitions().keySet()) {
				language.add(key);
			}
		}
		//AFD use this to minimize.
		AFN afd = convertToAFD();
		System.out.println(afd);
		afd = eliminateDuplicates(afd);
		return afd;
	}
	
	
	private AFN eliminateDuplicates(AFN afd)
	{
		AFN minimalAFD = (AFN)afd.clone();
		
		//minimalAFD;
		//Check states that have the same type
		ArrayList<ArrayList<AFNState>> candidates = new ArrayList<ArrayList<AFNState>>();
        String[] stateNames = minimalAFD.keySet().toArray(new String[]{} );
        for (int i = 0; i < stateNames.length; i++) {
        		ArrayList<AFNState> listOfCandidates = new ArrayList<AFNState>();
                AFNState state1 = minimalAFD.get(stateNames[i]);
                listOfCandidates.add(state1);
                for(int j=i+1; j<stateNames.length; j++){
                        
                        AFNState state2 = minimalAFD.get(stateNames[j]);
                        if(state1.equalsTypes(state2)){
                        	listOfCandidates.add(state2);
                        }
                }
                if(listOfCandidates.size()> 1){
                	candidates.add(listOfCandidates);
                }
        }
        
        ArrayList<ArrayList<AFNState>> candidates2 = new ArrayList<ArrayList<AFNState>>();
		int oldLen = candidates.size();
        do{
	        for (ArrayList<AFNState> arrayList : candidates) {
				ArrayList<AFNState> listOfCandidates = new ArrayList<AFNState>();
				listOfCandidates.add(arrayList.get(0));
				for (int i = 1; i < arrayList.size(); i++) {
					if(checkIfInCandidates(candidates, arrayList.get(0), arrayList.get(i))){
						listOfCandidates.add(arrayList.get(i));
					}
				}
				if(listOfCandidates.size()> 1){
                	candidates2.add(listOfCandidates);
                }
			}
	        oldLen = candidates.size();
	        candidates = candidates2;
	        candidates2 = new ArrayList<ArrayList<AFNState>>();
	        
		}while(candidates.size() != oldLen);
        
        removeDupGroups(candidates);
	    //System.out.println(candidates);
        for (ArrayList<AFNState> arrayList : candidates) {
        	updateMinimizedTransitions(minimalAFD, arrayList);
        }
        System.out.println(minimalAFD);  
	    
		return minimalAFD;
	}
	

	private void removeDupGroups (ArrayList<ArrayList<AFNState>> candidates){
		System.out.println("removing dup groups");
		ArrayList<ArrayList<AFNState>> candidateCopy = (ArrayList<ArrayList<AFNState>>)candidates.clone();
		Hashtable<String,Integer> firstLetters = new Hashtable<String,Integer>();
		for(int i =0; i < candidateCopy.size(); i++){
			ArrayList<AFNState> stateList = candidateCopy.get(i);
			firstLetters.put(stateList.get(0).getStateName(),i);
			//System.out.println(i + " " + stateList.get(0).getStateName() );
		}
		String[] stateNames = firstLetters.keySet().toArray(new String[]{} );
		ArrayList<ArrayList<AFNState>> toDelete = new ArrayList<ArrayList<AFNState>> ();
		for(ArrayList<AFNState> stateList: candidateCopy){
			
			for(int j=1; j< stateList.size(); j++){
				String includedStateName = stateList.get(j).getStateName();
				System.out.println("included state name" + includedStateName);
				for(int i =stateNames.length-1; i >=0; i--){
					String stateName = stateNames[i];
					System.out.println("first names" + stateName);
					if(includedStateName == stateName){
						System.out.println("removing the one at index" + firstLetters.get(stateName) );
						System.out.println("removing the one" + candidates.get(firstLetters.get(stateName)));
						toDelete.add(candidates.get(firstLetters.get(stateName)));
					}
				}
			}			
		}
		
		System.out.println(toDelete);
		candidates.removeAll(toDelete);
		
		System.out.println(candidates);
		
	}
	

	private void updateMinimizedTransitions(AFN afd, ArrayList<AFNState> arrayList){
		String newStateName = StringUtils.joinStateNames(",", arrayList);
		AFNState toReplace = afd.get(arrayList.get(0).getStateName());
		for (AFNState afnState : afd.values()) {
			for(AFNState stateToSearch: arrayList){
				for (String key : afnState.getTransitions().keySet()) {
					ArrayList<String> transition = afnState.getTransitions().get(key);
					for(int i=0; i<transition.size(); i++){
						System.out.println(transition.get(i)+" "+stateToSearch.getStateName());
						if(transition.get(i).equals(stateToSearch.getStateName())){
							transition.set(i, newStateName);
						}
					}
				}
			}
		}
		for(AFNState stateToSearch: arrayList){
			afd.remove(stateToSearch.getStateName());
		}
		toReplace.setStateName(newStateName);
		afd.addState(toReplace);
	}
	

	private boolean checkIfInCandidates(ArrayList<ArrayList<AFNState>> candidates, AFNState state1, AFNState state2){
		System.out.println("FROM: "+state1.getStateName() +"-"+state2.getStateName());
		boolean toReturn = true;
		for (String key : state1.getTransitions().keySet()) {
			boolean found = false;
			for (ArrayList<AFNState> arrayList : candidates) {
				String stateToSearchName = null;
				String trans1 = state1.getTransitions().get(key).get(0);
				String trans2 = state2.getTransitions().get(key).get(0);
				//System.out.println("TRANS: "+trans1 +"-"+trans2);
				if(trans1.equals(trans2)){
					found = true;
					break;
				}
				if(arrayList.get(0).getStateName().equals(trans1)){
					stateToSearchName = trans2;
				}else if(arrayList.get(0).getStateName().equals(trans2)){
					stateToSearchName = trans1;
				}
				//System.out.println("STATE NAME: "+arrayList.get(0).getStateName());
				//System.out.println(stateToSearchName);
				if(stateToSearchName != null){
					for (int i = 0; i < arrayList.size(); i++) {
						if(stateToSearchName.equals(arrayList.get(i).getStateName())){
							found = true;
							break;
						}
					}
					if(found){
						break;
					}
					
				}
			}
			if(!found){
				return false;
			}
		}
		return toReturn;
	}
	
	private AFN convertToAFD(){
		AFN afd = new AFN();
		
		//calculate epsilon closure
		for (AFNState state : this.values()) {
			if(!state.getTransitions().containsKey(epsilonClosure) && state.getTransitions().containsKey(epsilon)){
				calculateEpsilonClosure(state);
			}
		}
		//calculate direct transitions
		for (AFNState state : this.values()) {			
			if(state.getType() == AFNStateType.START || state.getType() == AFNStateType.START_FINAL){
				AFNState toAdd = calculateAFDState(afd, state);
				if(!afd.containsKey(toAdd.getStateName())){
					afd.put(state.getStateName(), toAdd);
				}
				break;
			}
		}
		return afd;
	}
	
	private void calculateEpsilonClosure(AFNState state){
		Boolean isLoop = false;
		state.setLock(true);
		//System.out.println("calculateEpsilonClosure: "+state.getStateName()+"-"+state.getTransitions().get(epsilon));
		//copy epsilon states to epsilonClosure
		state.getTransitions().put(epsilonClosure,(ArrayList<String>)state.getTransitions().get(epsilon).clone());
		
		//copy epsilon states from destiny epsilons
		for (String epsilonStateName : state.getTransitions().get(epsilon)) {
			AFNState epsilonState = get(epsilonStateName);
			if(!epsilonState.getTransitions().containsKey(epsilonClosure)){
				//check if it has epsilon states on destiny
				if(epsilonState.getTransitions().containsKey(epsilon)){
					//if we already visited that node dont add it... remember to remove the temp closure!
					if(epsilonState.getLock()){
						isLoop = true;
					}else{
						calculateEpsilonClosure(epsilonState);
						//if epsilonClosure dependant on a loop grab temp closure
						if(epsilonState.getTransitions().containsKey(epsilonClosureTemp)){
							state.getTransitions().put(epsilonClosure,combineTransitions(state, epsilonState, epsilonClosure, epsilonClosureTemp));
							state.getTransitions().remove(epsilonClosureTemp);
						}else{
							state.getTransitions().put(epsilonClosure,combineTransitions(state, epsilonState, epsilonClosure));
						}
					}
				}
			}else{
				state.getTransitions().put(epsilonClosure,combineTransitions(state, epsilonState, epsilonClosure));
			}
		}
		if(isLoop){
			state.getTransitions().put(epsilonClosureTemp, state.getTransitions().get(epsilonClosure));
			state.getTransitions().remove(epsilonClosure);
		}
		state.setLock(false);
	}
	
	private AFNState calculateAFDState(AFN afd, AFNState state){
		
		AFNState toReturn = (AFNState) state.clone();
		//loop for each transition "a", "b"...
		for (String key : language) {
			//dont add epsilons to AFD
			if(!key.equals(epsilon) && !key.equals(epsilonClosure)){
				if(!state.getTransitions().containsKey(key)){
					state.getTransitions().put(key, new ArrayList<String>());
				}
				//add epsilon states
				calculateTransitionsPlusEpsilon(state, key);
				
				ArrayList<String> transitions = state.getTransitions().get(key);
				String newStateName = StringUtils.join("", transitions);
				
				if(!afd.containsKey(newStateName) && newStateName.length()>0){
					combineStates(afd,newStateName, transitions);
				}
				ArrayList transList = new ArrayList<String>();
				transList.add(newStateName);
				toReturn.addTransition(key, transList);
			}
		}
		
		return toReturn;
	}
	
	private void calculateTransitionsPlusEpsilon(AFNState state, String transition){
		//System.out.println("calculateTransitionsPlusEpsilon"+state.getStateName()+":"+transition);
		if(state.getTransitions().containsKey(epsilonClosure)){
			for (String stateFromName : state.getTransitions().get(epsilonClosure)) {
				AFNState stateFrom = get(stateFromName);
				if(stateFrom.getTransitions().containsKey(transition)){
					state.getTransitions().put(transition,combineTransitions(state, stateFrom, transition));
					//System.out.println(stateFromName+"["+epsilonClosure+"]:"+stateFrom.getTransitions().containsKey(epsilonClosure));
				}
			}
		}
	}
	
	private void combineStates(AFN afd, String stateName, ArrayList<String> transitions){
		
		AFNState toReturn = this.get(transitions.get(0)).clone();
		toReturn.setStateName(stateName);
		Hashtable<String, HashSet<String>> trans = new Hashtable<String, HashSet<String>>();
		//combine transitions
		for (String stateToCombineName : transitions) {
			AFNState stateToCombine = get(stateToCombineName);
			toReturn.setType(getCombinedState(toReturn.getType(), stateToCombine.getType()));
			for (String key : language) {
				if(stateToCombine.getTransitions().containsKey(key)){
					if(!key.equals(epsilon) &&!key.equals(epsilonClosure)){
						if(!trans.containsKey(key)){
							trans.put(key, new HashSet<String>());
						}
						HashSet<String> set = trans.get(key);
						
						for (String s : stateToCombine.getTransition(key)) {
							set.add(s);
							AFNState destiny = get(s);
							if(destiny.getTransitions().containsKey(epsilonClosure)){
								for (String destinyEpsilon : destiny.getTransitions().get(epsilonClosure)) {
									set.add(destinyEpsilon);
								}
							}
						}
					}
				}else{
					stateToCombine.getTransitions().put(key, new ArrayList<String>());
				}
			}
		}
		Hashtable<String,ArrayList<String>> addLater = new Hashtable<String,ArrayList<String>>();
		//convert sets to arrays
		for (String key : trans.keySet()) {
			ArrayList<String> list = new ArrayList<String>();
			String sn = StringUtils.join("", trans.get(key));
			list.add( sn );
			toReturn.addTransition(key, list);
			if(!afd.containsKey(sn) && !stateName.equals(sn)){
				addLater.put(sn, ArrayUtils.convertToArrayList(trans.get(key)));
			}
			
		}
		afd.put(stateName, toReturn);
		for (String key : addLater.keySet()) {
			if(!afd.containsKey(key) && addLater.get(key).size()>0){
				combineStates(afd, key, addLater.get(key));
			}
		}
	}
	
	private ArrayList<String> combineTransitions(AFNState state1, AFNState state2, String input){
		return combineTransitions(state1, state2, input, input);
	}
	private ArrayList<String> combineTransitions(AFNState state1, AFNState state2, String input, String input2){
		HashSet<String> set = new HashSet<String>();
		for (String string : state1.getTransitions().get(input)) {
			set.add(string);
		}
		for (String string : state2.getTransitions().get(input2)) {
			set.add(string);
		}
		return ArrayUtils.convertToArrayList(set);
	}
	
	

	@Override
	public synchronized String toString() {
		String toReturn = "";
		for (AFNState state : this.values()) {
			toReturn+=state.toString()+",";
		}
		return toReturn;
	}
	
	protected static AFNStateType getCombinedState(AFNStateType type1, AFNStateType type2){
		AFNStateType toReturn = type1;
		if(type2 == AFNStateType.FINAL){
			toReturn = AFNStateType.FINAL;
		}else if(type2 == AFNStateType.NORMAL && type1 == AFNStateType.START){
			toReturn = AFNStateType.NORMAL;
		}
		return toReturn;
	}
	
	
}
